package com.kevinkk.monotonicstack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个整数数组 temperatures ，表示每天的温度
 * 返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 */

/**
 * ‼️单调栈‼️
 * 单调栈适用于解决在一个【一维数组】中要寻找任一个元素的右边或者左边【第一个】比自己大或者小的元素的位置
 * 单调栈就是用来存放我们遍历过的元素
 * 单调栈存放的元素为 【元素的下标】，这样做的好处是便于我们取数据
 * 单调栈可以是递增的也可以是递减的
 * 【当求第一个比元素大的数】时，需要是递增的，反之则是递减的
 */

public class DailyTemperatures {
    class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            Deque<Integer> st = new ArrayDeque<>(); // 单调栈
            int[] res = new int[temperatures.length];
            for (int i = 0; i < temperatures.length; i++) {
                // 每次遍历元素时，都和栈顶的元素（之前遍历过的元素）进行比较
                // 如果当前遍历的元素更大，那么就是找到了【比之前遍历过元素第一个大的元素】，可以记录其结果
                while (!st.isEmpty() && temperatures[i] > temperatures[st.peekFirst()]) {
                    int index = st.removeFirst();   // 之前遍历过的元素
                    res[index] = i - index;
                }
                // 单调栈中存储的是元素的下标
                st.addFirst(i);
            }
            return res;
        }
    }
}
